package com.leetcode.graph;

import java.util.*;

/**
 * @author Dennis Li
 * @date 2020/7/28 20:01
 */
public class CourseSchedule2_210 {

    public static int[] findOrder(int numCourses, int[][] prerequisites) {
        HashSet<Integer>[] adj = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new HashSet<>();
        }
        int[] inDegree = new int[numCourses];
        // [1,0] 0->1
        for (int[] pre : prerequisites) {
            inDegree[pre[0]]++;
            adj[pre[1]].add(pre[0]);
        }
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            // 加入入度为0的点
            if (inDegree[i] == 0) queue.offer(i);
        }
        int count = 0;
        int[] res = new int[numCourses];
        while (!queue.isEmpty()) {
            int now = queue.poll();
            // 按照拓扑排序，将这些点依次加入到数组中
            res[count] = now;
            count++;
            Set<Integer> set = adj[now];
            for (int v : set) {
                inDegree[v]--;
                if (inDegree[v] == 0) queue.offer(v);
            }
        }
        // 如果count与给定的数字个数不等，代表拓扑排序没有完成
        return numCourses != count ? new int[0] : res;
    }

    public int[] findOrder2(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return new int[0];
        }

        HashSet<Integer>[] adj = new HashSet[numCourses];
        for (int i = 0; i < numCourses; i++) {
            adj[i] = new HashSet<>();
        }

        // [1,0] 0 -> 1
        int[] inDegree = new int[numCourses];
        for (int[] p : prerequisites) {
            adj[p[1]].add(p[0]);
            inDegree[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            // 入度为0，添加结点
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        int[] res = new int[numCourses];
        // 当前结果集列表里的元素个数，正好可以作为下标
        int count = 0;

        while (!queue.isEmpty()) {
            // 当前入度为 0 的结点
            int head = queue.poll();
            res[count] = head;
            count++;
            // 遍历其入度结点，并减一
            Set<Integer> successors = adj[head];
            for (int nextCourse : successors) {
                inDegree[nextCourse]--;
                // 马上检测该结点的入度是否为 0，如果为 0，马上加入队列
                if (inDegree[nextCourse] == 0) {
                    queue.offer(nextCourse);
                }
            }
        }

        // 如果结果集中的数量不等于结点的数量，就不能完成课程任务，这一点是拓扑排序的结论
        if (count == numCourses) {
            return res;
        }
        return new int[0];
    }

    public int[] findOrder3(int numCourses, int[][] prerequisites) {
        if (numCourses <= 0) {
            return new int[0];
        }

        Set<Integer>[] adj = new Set[numCourses];

        for (int i = 0; i < numCourses; i++) {
            adj[i] = new HashSet<>();
        }

        int[] inDegree = new int[numCourses];

        for (int[] pre : prerequisites) {
            adj[pre[1]].add(pre[0]);
            inDegree[pre[0]]++;
        }
        Queue<Integer> queue = new LinkedList<>();

        for (int i = 0; i < numCourses; i++) {
            if (inDegree[i] == 0)
                queue.offer(i);
        }

        int[] res = new int[numCourses];
        int index = 0;

        while (!queue.isEmpty()) {
            int size = queue.size();
            while (size-- > 0) {
                int now = queue.poll();
                res[index++] = now;
                for (int num : adj[now]) {
                    inDegree[num]--;
                    if (inDegree[num] == 0)
                        queue.offer(num);
                }
            }
        }

        return index == numCourses ? res : new int[0];
    }

}
